two-valued logic

(Commonly known as "{Boolean algebra}") A mathematical

system concerning the two {truth values}, TRUE and FALSE and

the functions {AND}, {OR} and {NOT}. Two-valued logic is one

of the cornerstones of {logic} and is also fundamental in the

design of digital electronics and programming languages.

The term "Boolean" is used here with its common meaning -

two-valued, though strictly {Boolean algebra} is more general

than this.

Boolean functions are ususally represented by {truth tables}

where "0" represents "false" and "1" represents "true". E.g.:

A | B | A AND B

--:---:--------

0 | 0 | 0

0 | 1 | 0

1 | 0 | 0

1 | 1 | 1

This can be given more compactly using "x" to mean "don't

care" (either true or false):

A | B | A AND B

--:---:--------

0 | x | 0

x | 0 | 0

1 | 1 | 1

Similarly:

A | NOT A A | B | A OR B

--:------ --:---:--------

0 | 1 0 | 0 | 0

1 | 0 x | 1 | 1

1 | x | 1

Other functions such as {XOR}, {NAND}, {NOR} or functions or

more than two inputs can be constructed using combinations of

AND, OR and NOT. AND and OR can be constructed from each

other using {DeMorgan's Theorem}:

A OR B ◦ NOT ((NOT A) AND (NOT B))

A AND B ◦ NOT ((NOT A) OR (NOT B))

In fact any Boolean function can be constructed using just NOR

or just NAND using the identities:

NOT A ◦ A NOR A

A OR B ◦ NOT (A NOR B)

and {DeMorgan's Theorem}.

(1995-01-05)